package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-06-13 11:45
 */
public class 题库_0103_二叉树的锯齿形层序遍历 {

  static
  class Solution {

    private static final int DIRECTION_RIGHT = 0;

    private static final int DIRECTION_LEFT = 1;

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
      List<List<Integer>> answers = new ArrayList<>();
      if (root == null) {
        return answers;
      }
      int direction = DIRECTION_RIGHT;
      Deque<TreeNode> cur = new ArrayDeque<>();
      Deque<TreeNode> next = new ArrayDeque<>();
      cur.addLast(root);
      while (!cur.isEmpty()) {
        List<Integer> answer = new ArrayList<>();
        while (!cur.isEmpty()) {
          if (direction == DIRECTION_RIGHT) {
            root = cur.removeFirst();
            answer.add(root.val);
            if (root.left != null) {
              next.addLast(root.left);
            }
            if (root.right != null) {
              next.addLast(root.right);
            }
          } else {
            root = cur.removeLast();
            answer.add(root.val);
            if (root.right != null) {
              next.addFirst(root.right);
            }
            if (root.left != null) {
              next.addFirst(root.left);
            }
          }
        }
        answers.add(answer);
        Deque<TreeNode> temp = cur;
        cur = next;
        next = temp;
        direction = direction == DIRECTION_LEFT ? DIRECTION_RIGHT : DIRECTION_LEFT;
      }
      return answers;
    }
  }

}
